﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution84
{
    //先暴力一下,发现暴力都暴力不了,可以暴力，但是会超时
    //这个方法是枚举底的方法
    public int LargestRectangleArea2(int[] heights) { 
        int Max = 0;
        for (int i = 0; i < heights.Length; i++) {

            
            int curMin = heights[i];
        
        for (int j = i; j < heights.Length; j++)
            {//每次新加入的柱子，会导致产生两个新的面积
                //1，最低的高乘新的底
                //我们不需要考虑这么多。只要确保这个最大值我们遍历过就行
                //RectangleArea(heights, i, j);
                int width = j - i+1;
                curMin=Math.Min(curMin, heights[j]);


                Max= Math.Max(Max, width*curMin);


            }
        }

        return Max;

    }
    //写一下枚举高的方法
    public int LargestRectangleArea3(int[] heights)
    {
        int Max = 0;
        //遍历所有的高，找到以这个边为高的面积
        for (int cur = 0; cur < heights.Length; cur++)
        {

            int right = cur;
            int left = cur;
            while ((right+1)< heights.Length&& heights[right + 1] >= heights[cur])
            {
                //找到比他小的
                
                    right++;
   
            }
            while ((left - 1) >=0 && heights[left - 1] >= heights[cur])
            {
                //找到比他小的

                left--;

            }
            //虽然找到的是比当前高度小的，但是指针留在这两个高度左边和右边
            //所以cur才是高度最小的，所以作为底
            int width = right - left + 1;
           


            Max = Math.Max(Max, width * heights[cur]);

            Console.WriteLine(Max);



        }
        return Max;

        }


    //基于枚举高的方法，使用单调栈
    //我们的目的是找出cur当前柱子左边和右边小于curHeight的柱子
    //一次遍历，大于栈顶高度的入栈（栈顶就是左侧比当前小的柱子），大于当前柱子的都出栈，剩下的就是左侧比当前小的柱子
    public int LargestRectangleArea(int[] heights)
    {
    

        Stack<int> stack = new Stack<int>();//栈里面存的是index
        int[] left = new int[heights.Length];//左边比较低的
        left[0] = -1;
        stack.Push(0);
        for (int cur = 1; cur < heights.Length; cur++)//从左到右遍历
        {
            
            if (heights[cur] > heights[stack.Peek()])//入栈
            {
                
                left[cur]= stack.Peek();
                stack.Push(cur);
            }
            else
            {
                //出栈
                while (stack.Count > 0&& heights[cur] <= heights[stack.Peek()]) {

                    stack.Pop();
                   
                }
                if(stack.Count > 0)
                {
                    left[cur] = stack.Peek();
                    
                }
                else
                {
                    left[cur] = -1;
                }
                stack.Push(cur);
            }

        }

        Stack<int> stackR = new Stack<int>();//栈里面存的是index
        int[] right = new int[heights.Length];//左边比较低的
        
        for (int cur = heights.Length - 1; cur>=0; cur--)//从右到左
        {

            
                //出栈
                while (stackR.Count > 0 && heights[cur] <= heights[stackR.Peek()])
                {

                stackR.Pop();

                }
            if (stackR.Count > 0)
            {
                right[cur] = stackR.Peek();

            }
            else
            {
                right[cur] = heights.Length;//右边的最小值不是-1，而是自己，heights.Length-1，所以存heights.Length
            }
            
            stackR.Push(cur);
            

        }
        int Max = 0;
        //遍历所有的高，找到以这个边为高的面积
        for (int cur = 0; cur < heights.Length; cur++)
        {

            int rightIndex =right[ cur]-1;
            int leftIndex = left[cur]+1;
          
            //虽然找到的是比当前高度小的，但是指针留在这两个高度左边和右边
            //所以cur才是高度最小的，所以作为底
            int width = rightIndex - leftIndex + 1;



            Max = Math.Max(Max, width * heights[cur]);

            Console.WriteLine(Max);



        }
        return Max;
    }
    }

class Program84
{

    static void Main84(string[] args)
    {
        Solution84 solution = new Solution84();
        //int[] heights = [2, 1, 5, 6, 2, 3];
        int[] heights = [2, 4];
      int res=  solution.LargestRectangleArea(heights);
        Console.WriteLine(res);
    }

}